package com.ljy.my_study.leetcode.最大单词长度乘积;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @author lijunying
 * @date 2021/11/17 11:09
 */
public class TestMain {

//    给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
//
//             
//
//    示例 1:
//
//    输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
//    输出: 16
//    解释: 这两个单词为 "abcw", "xtfn"。
//    示例 2:
//
//    输入: ["a","ab","abc","d","cd","bcd","abcd"]
//    输出: 4
//    解释: 这两个单词为 "ab", "cd"。
//    示例 3:
//
//    输入: ["a","aa","aaa","aaaa"]
//    输出: 0
//    解释: 不存在这样的两个单词。
//             
//
//    提示：
//
//            2 <= words.length <= 1000
//            1 <= words[i].length <= 1000
//    words[i] 仅包含小写字母
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/maximum-product-of-word-lengths
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {

    }

    public int maxProduct(String[] words) {
        Map<Character, Set<Integer>> map=new HashMap<>();
        int len=words.length;
        for(int i=0;i<len;i++){
            String w=words[i];
            for(int j=0;j<w.length();j++){
                char c=w.charAt(j);
                Set<Integer> set= map.getOrDefault(c,new HashSet<>());
                set.add(i);
                map.put(c,set);
            }
        }
        int result=0;
        for(int i=0;i<len-1;i++){
            for(int j=i+1;j<len;j++){
                if(hasNotSameChar(words[i],j,map)){
                    result=Math.max(result,words[i].length()*words[j].length());
                }
            }
        }
        return result;
    }

    private boolean hasNotSameChar(String s1,int index,Map<Character,Set<Integer>> map){
        for(int i=0;i<s1.length();i++){
            Set<Integer> set= map.get(s1.charAt(i));
            if(set!=null&&set.contains(index)){
                return false;
            }
        }
        return true;
    }
}
